package binarysearch.test39;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/12 11:17
 */
public class Solution1 {

    // 递归二分查找思想
    public int divide(int m, int n) {
        long ans = bs((long) m, (long) n);
        if (ans == ((long) (Integer.MAX_VALUE)) + 1) {
            return Integer.MAX_VALUE;
        } else {
            return (int) ans;
        }
    }

    private long bs(long m, long n) {
        if (m == 0L) return 0L;
        boolean f = true;
        if (m < 0) f = !f;
        if (n < 0) f = !f;
        m = Math.abs(m);
        n = Math.abs(n);
        if (m < n) return 0L;
        long prem = m, pren = n;
        long ans = 1;
        m -= n;
        while (n <= m) {
            ans += ans;
            n += n;
            m -= n;
        }
        long a = ans + bs(prem - n, pren);
        return f ? a : -a;
    }
}
